package 力扣.动态规划;

import java.util.Arrays;
import java.util.Comparator;

public class 信封问题 {
    public static void main(String[] args) {
       int[][] envelops={{5,4},{6,4},{6,7},{2,3}};
        int i = maxEnvelopes(envelops);
        System.out.println(i);
    }
    public static int maxEnvelopes(int[][] envelops){
        //思路，对宽进行升序排序，如果宽相同，则对高进行降序排序
        int n=envelops.length;
        Arrays.sort(envelops, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
            }
        });
        int[] h = new int[envelops.length];
        for (int i = 0; i < envelops.length; i++) {
            h[i]=envelops[i][1];
        }
        //求h数组中的最大升序排列
        return lengthOfLIS(h);
    }
    public static int lengthOfLIS(int[] h){
        int[] dp = new int[h.length];
        //将dp数组都填充为1
        Arrays.fill(dp,1);
        int res=1;
        for (int i = 1; i < h.length; i++) {
            for (int j = 0; j < i; j++) {
                if (h[j]<h[i])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}
